/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class SplitLinkedListinParts {
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
		}
	}

	public ListNode[] splitListToParts(ListNode root, int k) {
		ListNode cur = root;
		int n = 0;
		while (cur != null) {
			n++;
			cur = cur.next;
		}
		int s = n / k;
		int f = n % k;
		ListNode[] res = new ListNode[k];
		// 前面f个有s+1个
		int curIndex = 0;
		cur = root;
		if (f != 0) {
			s++;
		}
		while (curIndex < k) {
			res[curIndex++] = cur;
			for (int count = 0; count < s; count++) {
				if (count == s - 1) {// 最后要置位null
					ListNode tmp = cur.next;
					cur.next = null;
					cur = tmp;
				} else {
					cur = cur.next;
				}
			}
			if (curIndex == f) {
				s--;
			}
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
